ebab7d0da53c51438720d60c6e2e467c - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Java ConcurrentMap</title>

</head>

Java ConcurrentMap

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

The Java programming language's <a href="Java_Collections_Framework" class="mw-redirect" title="Java Collections Framework">Java Collections Framework</a> version 1.5 and later defines and implements the original regular single-threaded Maps, and

also new thread-safe Maps implementing the <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/concurrent/ConcurrentMap.html">java.util.concurrent.ConcurrentMap</a></code> interface among other concurrent interfaces.<a href="#cite_note-FOOTNOTEGoetzPeierlsBlochBowbeer200684–85§5.2_Concurrent_collections-1">[1]</a>

In Java 1.6, the <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/NavigableMap.html">java.util.NavigableMap</a></code> interface was added, extending <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/SortedMap.html">java.util.SortedMap</a></code>,

and the <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/concurrent/ConcurrentNavigableMap.html">java.util.concurrent.ConcurrentNavigableMap</a></code> interface was added as a subinterface combination.

<div class="mw-heading mw-heading2"><h2 id="Java_Map_Interfaces">Java Map Interfaces</h2></div>

The version 1.8 Map interface diagram has the shape below. Sets can be considered sub-cases of corresponding Maps in which the values are always a particular constant which can be ignored, although the Set API uses corresponding but differently named methods. At the bottom is the <code>java.util.concurrent.ConcurrentNavigableMap</code>, which is a multiple-inheritance.

<ul><li><code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/Collection.html">java.util.Collection</a></code>

<ul><li><code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/SortedMap.html">java.util.SortedMap</a></code>

<ul><li><code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/NavigableMap.html">java.util.NavigableMap</a></code>

<ul><li><code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/concurrent/ConcurrentNavigableMap.html">java.util.concurrent.ConcurrentNavigableMap</a></code></li></ul></li></ul></li>

<li><code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/concurrent/ConcurrentMap.html">java.util.concurrent.ConcurrentMap</a></code>

<div class="mw-heading mw-heading2"><h2 id="Implementations">Implementations</h2></div>

<div class="mw-heading mw-heading3"><h3 id="ConcurrentHashMap">ConcurrentHashMap</h3></div>

For unordered access as defined in the <code>java.util.Map</code> interface, the <code>java.util.concurrent.ConcurrentHashMap</code> implements <code>java.util.concurrent.ConcurrentMap</code>.<a href="#cite_note-FOOTNOTEGoetzPeierlsBlochBowbeer200685–86§5.2.1_ConcurrentHashMap-2">[2]</a> The mechanism is a hash access to a hash table with lists of entries, each entry holding a key, a value, the hash, and a next reference. Previous to Java 8, there were multiple locks each serializing access to a 'segment' of the table. In Java 8, native synchronization is used on the heads of the lists themselves, and the lists can mutate into small trees when they threaten to grow too large due to unfortunate hash collisions. Also, Java 8 uses the compare-and-set primitive optimistically to place the initial heads in the table, which is very fast. Performance is O(n), but there are delays occasionally when rehashing is necessary. After the hash table expands, it never shrinks, possibly leading to a memory 'leak' after entries are removed.

<div class="mw-heading mw-heading3"><h3 id="ConcurrentSkipListMap">ConcurrentSkipListMap</h3></div>

For ordered access as defined by the <code>java.util.NavigableMap</code> interface, <code>java.util.concurrent.ConcurrentSkipListMap</code> was added in Java 1.6,<a href="#cite_note-FOOTNOTEGoetzPeierlsBlochBowbeer200684–85§5.2_Concurrent_collections-1">[1]</a> and implements <code>java.util.concurrent.ConcurrentMap</code> and also <code>java.util.concurrent.ConcurrentNavigableMap</code>. It is a <a href="Skip_list" title="Skip list">Skip list</a> which uses Lock-free techniques to make a tree. Performance is O(log(n)).

<div class="mw-heading mw-heading3"><h3 id="Ctrie">Ctrie</h3></div>

<ul><li><a rel="nofollow" class="external text" href="https://github.com/romix/java-concurrent-hash-trie-map">Ctrie</a> A <a href="Trie" title="Trie">trie</a>-based Lock-free tree.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Concurrent_modification_problem">Concurrent modification problem</h2></div>

One problem solved by the Java 1.5 <code>java.util.concurrent</code> package is that of concurrent modification. The collection classes it provides may be reliably used by multiple Threads.

All Thread-shared non-concurrent Maps and other collections need to use some form of explicit locking such as native synchronization in order to prevent concurrent modification, or else there must be a way to prove from the program logic that concurrent modification cannot occur. Concurrent modification of a <code>Map</code> by multiple Threads will sometimes destroy the internal consistency of the data structures inside the <code>Map</code>, leading to bugs which manifest rarely or unpredictably, and which are difficult to detect and fix. Also, concurrent modification by one Thread with read access by another Thread or Threads will sometimes give unpredictable results to the reader, although the Map's internal consistency will not be destroyed. Using external program logic to prevent concurrent modification increases code complexity and creates an unpredictable risk of errors in existing and future code, although it enables non-concurrent Collections to be used. However, either locks or program logic cannot coordinate external threads which may come in contact with the <code>Collection</code>.

<div class="mw-heading mw-heading3"><h3 id="Modification_counters">Modification counters</h3></div>

In order to help with the concurrent modification problem, the non-concurrent <code>Map</code> implementations and other <code>Collection</code>s use internal modification counters which are consulted before and after a read to watch for changes: the writers increment the modification counters. A concurrent modification is supposed to be detected by this mechanism, throwing a <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/ConcurrentModificationException.html">java.util.ConcurrentModificationException</a></code>,<a href="#cite_note-FOOTNOTEGoetzPeierlsBlochBowbeer200682–83§5.1.2_Iterators_and_ConcurrentModificationException-3">[3]</a> but it is not guaranteed to occur in all cases and should not be relied on. The counter maintenance is also a performance reducer. For performance reasons, the counters are not volatile, so it is not guaranteed that changes to them will be propagated between <code>Thread</code>s.

<div class="mw-heading mw-heading3"><h3 id="Collections.synchronizedMap()">Collections.synchronizedMap()</h3></div>

One solution to the concurrent modification problem is using a particular wrapper class provided by a factory in <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/Collections.html">java.util.Collections</a></code> : <a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/Collections.html#synchronizedMap(java.util.Map)"><code>public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m)</code></a> which wraps an existing non-thread-safe <code>Map</code> with methods that synchronize on an internal mutex.<a href="#cite_note-FOOTNOTEGoetzPeierlsBlochBowbeer200684–85§5.2.1_ConcurrentHashMap-4">[4]</a> There are also wrappers for the other kinds of Collections. This is a partial solution, because it is still possible that the underlying <code>Map</code> can be inadvertently accessed by <code>Thread</code>s which keep or obtain unwrapped references. Also, all Collections implement the <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/lang/Iterable.html">java.lang.Iterable</a></code> but the synchronized-wrapped Maps and other wrapped <code>Collections</code> do not provide synchronized iterators, so the synchronization is left to the client code, which is slow and error prone and not possible to expect to be duplicated by other consumers of the synchronized <code>Map</code>. The entire duration of the iteration must be protected as well. Furthermore, a <code>Map</code> which is wrapped twice in different places will have different internal mutex Objects on which the synchronizations operate, allowing overlap. The delegation is a performance reducer, but modern Just-in-Time compilers often inline heavily, limiting the performance reduction. Here is how the wrapping works inside the wrapper - the mutex is just a final <code>Object</code> and m is the final wrapped <code>Map</code>:

<div class="mw-highlight mw-highlight-lang-java mw-content-ltr" dir="ltr"><pre> public V put(K key, V value) {

synchronized (mutex) {

return m.put(key, value);

}

</pre></div>

The synchronization of the iteration is recommended as follows; however, this synchronizes on the wrapper rather than on the internal mutex, allowing overlap:<a href="#cite_note-5">[5]</a>

<div class="mw-highlight mw-highlight-lang-java mw-content-ltr" dir="ltr"><pre> Map<String, String> wrappedMap = Collections.synchronizedMap(map);

...

synchronized (wrappedMap) {

for (final String s : wrappedMap.keySet()) {

// some possibly long operation executed possibly

// many times, delaying all other accesses

}

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Native_synchronization">Native synchronization</h3></div>

Any <code>Map</code> can be used safely in a multi-threaded system by ensuring that all accesses to it are handled by the Java synchronization mechanism:

<div class="mw-highlight mw-highlight-lang-java mw-content-ltr" dir="ltr"><pre> final Map<String, String> map = new HashMap<>();

...

// Thread A

// Use the map itself as the lock. Any agreed object can be used instead.

synchronized(map) {

map.put("key","value");

}

..

// Thread B

synchronized (map) {

String result = map.get("key");

...

}

...

// Thread C

for (final Entry<String, String> s : map.entrySet()) {

/*

* Some possibly slow operation, delaying all other supposedly fast operations.

* Synchronization on individual iterations is not possible.

*/

...

}

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="ReentrantReadWriteLock">ReentrantReadWriteLock</h3></div>

The code using a <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/concurrent/ReentrantReadWriteLock.html">java.util.concurrent.ReentrantReadWriteLock</a></code> is similar to that for native synchronization. However, for safety, the locks should be used in a try/finally block so that early exit such as <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/lang/Exception.html">java.lang.Exception</a></code> throwing or break/continue will be sure to pass through the unlock. This technique is better than using synchronization<a href="#cite_note-FOOTNOTEGoetzPeierlsBlochBowbeer200695–98§13.5_Read-write_locks-6">[6]</a> because reads can overlap each other, there is a new issue in deciding how to prioritize the writes with respect to the reads. For simplicity a <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/concurrent/ReentrantLock.html">java.util.concurrent.ReentrantLock</a></code> can be used instead, which makes no read/write distinction. More operations on the locks are possible than with synchronization, such as <code>tryLock()</code> and <code>tryLock(long timeout, TimeUnit unit)</code>.

<div class="mw-highlight mw-highlight-lang-java mw-content-ltr" dir="ltr"><pre> final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();

final ReadLock readLock = lock.readLock();

final WriteLock writeLock = lock.writeLock();

..

// Thread A

try {

writeLock.lock();

...

} finally {

writeLock.unlock();

}

...

// Thread B

try {

readLock.lock();

final String s = map.get("key");

..

} finally {

readLock.unlock();

}

// Thread C

try {

readLock.lock();

for (final Entry<String, String> s : map.entrySet()) {

/*

* Some possibly slow operation, delaying all other supposedly fast operations.

* Synchronization on individual iterations is not possible.

*/

...

}

} finally {

readLock.unlock();

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Convoys">Convoys</h2></div>

Mutual exclusion has a <a href="Lock_convoy" title="Lock convoy">lock convoy</a> problem, in which threads may pile up on a lock, causing the JVM to need to maintain expensive queues of waiters and to 'park' the waiting <code>Thread</code>s. It is expensive to park and unpark a <code>Thread</code>s, and a slow context switch may occur. Context switches require from microseconds to milliseconds, while the Map's own basic operations normally take nanoseconds. Performance can drop to a small fraction of a single <code>Thread</code>'s throughput as contention increases. When there is no or little contention for the lock, there is little performance impact; however, except for the lock's contention test. Modern JVMs will inline most of the lock code, reducing it to only a few instructions, keeping the no-contention case very fast. Reentrant techniques like native synchronization or <code>java.util.concurrent.ReentrantReadWriteLock</code> however have extra performance-reducing baggage in the maintenance of the reentrancy depth, affecting the no-contention case as well. The Convoy problem seems to be easing with modern JVMs, but it can be hidden by slow context switching: in this case, latency will increase, but throughput will continue to be acceptable. With hundreds of <code>Thread</code>s , a context switch time of 10ms produces a latency in seconds.

<div class="mw-heading mw-heading2"><h2 id="Multiple_cores">Multiple cores</h2></div>

Mutual exclusion solutions fail to take advantage of all of the computing power of a multiple-core system, because only one <code>Thread</code> is allowed inside the <code>Map</code> code at a time. The implementations of the particular concurrent Maps provided by the Java Collections Framework and others sometimes take advantage of multiple cores using <a href="Lock_free" class="mw-redirect" title="Lock free">lock free</a> programming techniques. Lock-free techniques use operations like the compareAndSet() intrinsic method available on many of the Java classes such as <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/concurrent/AtomicReference.html">AtomicReference</a></code> to do conditional updates of some Map-internal structures atomically. The compareAndSet() primitive is augmented in the JCF classes by native code that can do compareAndSet on special internal parts of some Objects for some algorithms (using 'unsafe' access). The techniques are complex, relying often on the rules of inter-thread communication provided by volatile variables, the happens-before relation, special kinds of lock-free 'retry loops' (which are not like spin locks in that they always produce progress). The compareAndSet() relies on special processor-specific instructions. It is possible for any Java code to use for other purposes the compareAndSet() method on various concurrent classes to achieve Lock-free or even Wait-free concurrency, which provides finite latency. Lock-free techniques are simple in many common cases and with some simple collections like stacks.

The diagram indicates how synchronizing using <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/Collections.html#synchronizedMap(java.util.Map)">Collections.synchronizedMap(java.util.Map)</a></code>wrapping a regular HashMap (purple) may not scale as well as ConcurrentHashMap (red). The others are the ordered ConcurrentNavigableMaps AirConcurrentMap (blue) and ConcurrentSkipListMap (CSLM green). (The flat spots may be rehashes producing tables that are bigger than the Nursery, and ConcurrentHashMap takes more space. Note y axis should say 'puts K'. System is 8-core i7 2.5 GHz, with -Xms5000m to prevent GC). GC and JVM process expansion change the curves considerably, and some internal lock-Free techniques generate garbage on contention.

<div class="mw-heading mw-heading2"><h2 id="Predictable_latency">Predictable latency</h2></div>

Yet another problem with mutual exclusion approaches is that the assumption of complete atomicity made by some single-threaded code creates sporadic unacceptably long inter-Thread delays in a concurrent environment. In particular, Iterators and bulk operations like putAll() and others can take a length of time proportional to the Map size, delaying other <code>Thread</code>s that expect predictably low latency for non-bulk operations. For example, a multi-threaded web server cannot allow some responses to be delayed by long-running iterations of other threads executing other requests that are searching for a particular value. Related to this is the fact that <code>Thread</code>s that lock the <code>Map</code> do not actually have any requirement ever to relinquish the lock, and an infinite loop in the owner <code>Thread</code> may propagate permanent blocking to other <code>Thread</code>s . Slow owner <code>Thread</code>s can sometimes be Interrupted. Hash-based Maps also are subject to spontaneous delays during rehashing.

<div class="mw-heading mw-heading2"><h2 id="Weak_consistency">Weak consistency</h2></div>

The <code>java.util.concurrent</code> packages' solution to the concurrent modification problem, the convoy problem, the predictable latency problem, and the multi-core problem includes an architectural choice called weak consistency. This choice means that reads like <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/Map.html#get(java.lang.Object)">get(java.lang.Object)</a></code> will not block even when updates are in progress, and it is allowable even for updates to overlap with themselves and with reads. Weak consistency allows, for example, the contents of a <code>ConcurrentMap</code> to change during an iteration of it by a single <code>Thread</code>.<a href="#cite_note-FOOTNOTEGoetzPeierlsBlochBowbeer200685–86§5.21_ConcurrentHashMap-7">[7]</a> The Iterators are designed to be used by one <code>Thread</code> at a time. So, for example, a <code>Map</code> containing two entries that are inter-dependent may be seen in an inconsistent way by a reader <code>Thread</code> during modification by another <code>Thread</code>. An update that is supposed to change the key of an Entry (k1,v) to an Entry (k2,v) atomically would need to do a remove(k1) and then a put(k2, v), while an iteration might miss the entry or see it in two places. Retrievals return the value for a given key that reflects the latest previous completed update for that key. Thus there is a 'happens-before' relation.

There is no way for <code>ConcurrentMap</code>s to lock the entire table. There is no possibility of <code>ConcurrentModificationException</code> as there is with inadvertent concurrent modification of non-concurrent <code>Map</code>s. The <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/Map.html#size()">size()</a></code> method may take a long time, as opposed to the corresponding non-concurrent <code>Map</code>s and other collections which usually include a size field for fast access, because they may need to scan the entire <code>Map</code> in some way. When concurrent modifications are occurring, the results reflect the state of the <code>Map</code> at some time, but not necessarily a single consistent state, hence <code>size()</code>, <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/Map.html#isEmpty()">isEmpty()</a></code> and <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/Map.html#containsValue(java.lang.Object)">containsValue(java.lang.Object)</a></code> may be best used only for monitoring.

<div class="mw-heading mw-heading2"><h2 id="ConcurrentMap_1.5_methods">ConcurrentMap 1.5 methods</h2></div>

There are some operations provided by <code>ConcurrentMap</code> that are not in <code>Map</code> - which it extends - to allow atomicity of modifications. The replace(K, v1, v2) will test for the existence of v1 in the Entry identified by K and only if found, then the v1 is replaced by v2 atomically. The new replace(k,v) will do a put(k,v) only if k is already in the Map. Also, putIfAbsent(k,v) will do a put(k,v) only if k is not already in the <code>Map</code>, and remove(k, v) will remove the Entry for v only if v is present. This atomicity can be important for some multi-threaded use cases, but is not related to the weak-consistency constraint.

For <code>ConcurrentMap</code>s, the following are atomic.

m.putIfAbsent(k, v) is atomic but equivalent to:

<div class="mw-highlight mw-highlight-lang-java mw-content-ltr" dir="ltr"><pre> if (k == null || v == null)

throw new NullPointerException();

if (!m.containsKey(k)) {

return m.put(k, v);

} else {

return m.get(k);

}

</pre></div>

m.replace(k, v) is atomic but equivalent to:

throw new NullPointerException();

return m.put(k, v);

} else {

return null;

}

</pre></div>

m.replace(k, v1, v2) is atomic but equivalent to:

<div class="mw-highlight mw-highlight-lang-java mw-content-ltr" dir="ltr"><pre> if (k == null || v1 == null || v2 == null)

throw new NullPointerException();

if (m.containsKey(k) && Objects.equals(m.get(k), v1)) {

m.put(k, v2);

return true;

} else

return false;

}

</pre></div>

m.remove(k, v) is atomic but equivalent to:

<div class="mw-highlight mw-highlight-lang-java mw-content-ltr" dir="ltr"><pre> // if Map does not support null keys or values (apparently independently)

if (k == null || v == null)

throw new NullPointerException();

if (m.containsKey(k) && Objects.equals(m.get(k), v)) {

m.remove(k);

return true;

} else

return false;

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="ConcurrentMap_1.8_methods">ConcurrentMap 1.8 methods</h2></div>

Because <code>Map</code> and <code>ConcurrentMap</code> are interfaces, new methods cannot be added to them without breaking implementations. However, Java 1.8 added the capability for default interface implementations and it added to the <code>Map</code> interface default implementations of some new methods getOrDefault(Object, V), forEach(BiConsumer), replaceAll(BiFunction), computeIfAbsent(K, Function), computeIfPresent(K, BiFunction), compute(K,BiFunction), and merge(K, V, BiFunction). The default implementations in <code>Map</code> do not guarantee atomicity, but in the <code>ConcurrentMap</code> overriding defaults these use <a href="Lock_free" class="mw-redirect" title="Lock free">Lock free</a> techniques to achieve atomicity, and existing ConcurrentMap implementations will automatically be atomic. The lock-free techniques may be slower than overrides in the concrete classes, so concrete classes may choose to implement them atomically or not and document the concurrency properties.

<div class="mw-heading mw-heading2"><h2 id="Lock-free_atomicity">Lock-free atomicity</h2></div>

It is possible to use <a href="Lock-free" class="mw-redirect" title="Lock-free">lock-free</a> techniques with ConcurrentMaps because they include methods of a <a href="Consensus_(computer_science)#Consensus_number" title="Consensus (computer science)">sufficiently high consensus number, namely infinity</a>, meaning that any number of <code>Thread</code>s may be coordinated. This example could be implemented with the Java 8 merge() but it shows the overall lock-free pattern, which is more general. This example is not related to the internals of the ConcurrentMap but to the client code's use of the ConcurrentMap. For example, if we want to multiply a value in the Map by a constant C atomically:

<div class="mw-highlight mw-highlight-lang-java mw-content-ltr" dir="ltr"><pre> static final long C = 10;

void atomicMultiply(ConcurrentMap<Long, Long> map, Long key) {

for (;;) {

Long oldValue = map.get(key);

// Assuming oldValue is not null. This is the 'payload' operation, and should not have side-effects due to possible re-calculation on conflict

if (map.replace(key, oldValue, newValue))

break;

}

</pre></div>

The putIfAbsent(k, v) is also useful when the entry for the key is allowed to be absent. This example could be implemented with the Java 8 compute() but it shows the overall lock-free pattern, which is more general. The replace(k,v1,v2) does not accept null parameters, so sometimes a combination of them is necessary. In other words, if v1 is null, then putIfAbsent(k, v2) is invoked, otherwise replace(k,v1,v2) is invoked.

<div class="mw-highlight mw-highlight-lang-java mw-content-ltr" dir="ltr"><pre> void atomicMultiplyNullable(ConcurrentMap<Long, Long> map, Long key) {

for (;;) {

// This is the 'payload' operation, and should not have side-effects due to possible re-calculation on conflict

Long newValue = oldValue == null ? INITIAL_VALUE : oldValue * C;

if (replaceNullable(map, key, oldValue, newValue))

break;

}

...

static boolean replaceNullable(ConcurrentMap<Long, Long> map, Long key, Long v1, Long v2) {

return v1 == null ? map.putIfAbsent(key, v2) == null : map.replace(key, v1, v2);

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

The Java collections framework was designed and developed primarily by <a href="Joshua_Bloch" title="Joshua Bloch">Joshua Bloch</a>, and was introduced in <a href="J2SE_1.2" class="mw-redirect" title="J2SE 1.2">JDK 1.2</a>.<a href="#cite_note-8">[8]</a> The original concurrency classes came from <a href="Doug_Lea" title="Doug Lea">Doug Lea</a>'s <a href="#cite_note-douglea2-9">[9]</a> collection package.

<ul><li><a href="Java_Collections_Framework" class="mw-redirect" title="Java Collections Framework">Java Collections Framework</a></li>

<li><a href="Container_(data_structure)" class="mw-redirect" title="Container (data structure)">Container (data structure)</a></li>

<li><a href="Java_concurrency" title="Java concurrency">Java concurrency</a></li>

<div class="mw-heading mw-heading2"><h2 id="Citations">Citations</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-FOOTNOTEGoetzPeierlsBlochBowbeer200684–85§5.2_Concurrent_collections-1">^ <a href="#cite_ref-FOOTNOTEGoetzPeierlsBlochBowbeer200684–85§5.2_Concurrent_collections_1-0">a</a> <a href="#cite_ref-FOOTNOTEGoetzPeierlsBlochBowbeer200684–85§5.2_Concurrent_collections_1-1">b</a> <a href="#CITEREFGoetzPeierlsBlochBowbeer2006">Goetz et al. 2006</a>, pp. 84–85, §5.2 Concurrent collections.

</li>

<li id="cite_note-FOOTNOTEGoetzPeierlsBlochBowbeer200685–86§5.2.1_ConcurrentHashMap-2"><a href="#cite_ref-FOOTNOTEGoetzPeierlsBlochBowbeer200685–86§5.2.1_ConcurrentHashMap_2-0">^</a> <a href="#CITEREFGoetzPeierlsBlochBowbeer2006">Goetz et al. 2006</a>, pp. 85–86, §5.2.1 ConcurrentHashMap.

</li>

<li id="cite_note-FOOTNOTEGoetzPeierlsBlochBowbeer200682–83§5.1.2_Iterators_and_ConcurrentModificationException-3"><a href="#cite_ref-FOOTNOTEGoetzPeierlsBlochBowbeer200682–83§5.1.2_Iterators_and_ConcurrentModificationException_3-0">^</a> <a href="#CITEREFGoetzPeierlsBlochBowbeer2006">Goetz et al. 2006</a>, pp. 82–83, §5.1.2 Iterators and ConcurrentModificationException.

</li>

<li id="cite_note-FOOTNOTEGoetzPeierlsBlochBowbeer200684–85§5.2.1_ConcurrentHashMap-4"><a href="#cite_ref-FOOTNOTEGoetzPeierlsBlochBowbeer200684–85§5.2.1_ConcurrentHashMap_4-0">^</a> <a href="#CITEREFGoetzPeierlsBlochBowbeer2006">Goetz et al. 2006</a>, pp. 84–85, §5.2.1 ConcurrentHashMap.

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Collections.html#synchronizedMap(java.util.Map)">"java.util.Collections.synchronizedMap"</a>. Java / Java SE / 11 / API / java.base. Oracle Help Center. September 19, 2018. Retrieved 2020-07-17.</cite>

</li>

<li id="cite_note-FOOTNOTEGoetzPeierlsBlochBowbeer200695–98§13.5_Read-write_locks-6"><a href="#cite_ref-FOOTNOTEGoetzPeierlsBlochBowbeer200695–98§13.5_Read-write_locks_6-0">^</a> <a href="#CITEREFGoetzPeierlsBlochBowbeer2006">Goetz et al. 2006</a>, pp. 95–98, §13.5 Read-write locks.

</li>

<li id="cite_note-FOOTNOTEGoetzPeierlsBlochBowbeer200685–86§5.21_ConcurrentHashMap-7"><a href="#cite_ref-FOOTNOTEGoetzPeierlsBlochBowbeer200685–86§5.21_ConcurrentHashMap_7-0">^</a> <a href="#CITEREFGoetzPeierlsBlochBowbeer2006">Goetz et al. 2006</a>, pp. 85–86, §5.21 ConcurrentHashMap.

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFVanhelsuwé1999" class="citation web cs1">Vanhelsuwé, Laurence (January 1, 1999). <a rel="nofollow" class="external text" href="https://www.infoworld.com/article/2076326/the-battle-of-the-container-frameworks--which-should-you-use-.html">"The battle of the container frameworks: which should you use?"</a>. <a href="JavaWorld" class="mw-redirect" title="JavaWorld">JavaWorld</a>. Retrieved 2020-07-17.</cite>

</li>

<li id="cite_note-douglea2-9"><a href="#cite_ref-douglea2_9-0">^</a> <cite id="CITEREFLea" class="citation web cs1"><a href="Doug_Lea" title="Doug Lea">Lea, Doug</a>. <a rel="nofollow" class="external text" href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html">"Overview of package util.concurrent Release 1.3.4"</a>. Retrieved 2011-01-01.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFGoetzPeierlsBlochBowbeer2006" class="citation book cs1">Goetz, Brian; Peierls, Tim; Bloch, Joshua; Bowbeer, Joseph; Holmes, David; Lea, Doug (2006). <a rel="nofollow" class="external text" href="https://archive.org/details/javaconcurrencyi00goet">Java Concurrency in Practice</a>. Addison Wesley. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-321-34960-1</bdi>. <a href="OL_(identifier)" class="mw-redirect" title="OL (identifier)">OL</a> <a rel="nofollow" class="external text" href="https://openlibrary.org/books/OL25208908M">25208908M</a>.</cite></li>

<li><cite id="CITEREFLea1999" class="citation book cs1">Lea, Doug (1999). Concurrent Programming in Java: Design Principles and Patterns. Addison Wesley. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-31009-0</bdi>. <a href="OL_(identifier)" class="mw-redirect" title="OL (identifier)">OL</a> <a rel="nofollow" class="external text" href="https://openlibrary.org/books/OL55044M">55044M</a>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style>

<div class="side-box-text plainlist">The Wikibook <a href="https://en.wikibooks.org/wiki/Java_Programming" class="extiw external" title="wikibooks:Java Programming">Java Programming</a> has a page on the topic of: <a href="https://en.wikibooks.org/wiki/Java_Programming/Collections" class="extiw external" title="wikibooks:Java Programming/Collections">Collections</a></div></div>

</div>

<ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20150306171304/http://javalessons.com/cgi-bin/fun/java-tutorials-main.cgi?sub=adv&ses=ao789">Collections Lessons</a></li>

<li><a rel="nofollow" class="external text" href="http://tutorials.jenkov.com/java-collections/index.html">Java 6 Collection Tutorial</a> — By Jakob Jenkov, Kadafi Kamphulusa</li>

<li><a rel="nofollow" class="external text" href="http://www-128.ibm.com/developerworks/java/library/j-tiger07195/">Taming Tiger: The Collections Framework</a></li>

<li><a rel="nofollow" class="external text" href="https://docs.oracle.com/javase/8/docs/technotes/guides/collections/index.html">'The Collections Framework'</a> (Oracle Java SE 8 documentation)</li>

<li><a rel="nofollow" class="external text" href="http://docs.oracle.com/javase/tutorial/collections/">'The Java Tutorials - Collections' by Josh Bloch</a></li>

<li><a rel="nofollow" class="external text" href="https://stackoverflow.com/q/21974361/3049628">What Java Collection should I use?</a> — A handy flowchart to simplify selection of collections</li>

<li><a rel="nofollow" class="external text" href="http://www.janeve.me/articles/which-java-collection-to-use">'Which Java Collection to use?'</a> — by Janeve George</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-04-30" href="https://en.wikipedia.org/wiki/?title=Java_ConcurrentMap&oldid=1221496612">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>